#include <stdio.h>
#include <stdlib.h>
#include "qs.h"

#define SEED 23 


int main(int argc, char **argv)
{
  int size, seed, *array;

  double start, end, diff;
  struct timeval t1,
                 t2;

  if (argc < 2) {
    printf("Usage:\n   %s [-r] <input_length>\n", argv[0]);
    exit(-1);
  }
  
  if (argc == 2) {
    size = atoi(argv[1]);
    printf("Normal sorting\n");
  }
  else {
    if (strcmp(argv[1], "-r") != 0) {
       printf("Unknown option (%s)\n", argv[1]);
       exit(-1);
    }
    printf("Reverse sorting\n");
    size = atoi(argv[2]);
  }
 
  array = (int *)malloc(size * sizeof(int));

  initialize(array, size, SEED);
  
  gettimeofday(&t1, NULL);
  
  qsSeq(array, 0, size-1);

  gettimeofday(&t2, NULL);

  /* Calculate process duration */
  start = (double)(t1.tv_sec * 1.0e6) + (double)t1.tv_usec;
  end   = (double)(t2.tv_sec * 1.0e6) + (double)t2.tv_usec;
  diff  = (end - start) / 1.0e6;

  /* Show process time */
  printf("Time: %f\n", diff);
  printf("Length of array: %d\n", size);

  free(array);

  return(0);
} /* main */



/****************************************************************************
 * Description: Sets randomly the values for the array
 * Parameters:
 *  int *v: vector to initialize
 *      seed:   seed for random generator
****************************************************************************/
void initialize(int *v, int size, int seed) {
  unsigned i;

   printf("Seed: %d size: %d\n", seed, size); 
   srandom(seed);
   for(i = 0; i < size; i++)
     v[i] = (int)random();
}
/****************************************************************************
* Description: writes the array
* Parameters:
*  int *v: vector to write
****************************************************************************/
void write_array(int *v, int size) {
  unsigned i;

  for(i = 0; i < size; i++)
    printf("v[%u] = %i\n", i, v[i]);
}
/****************************************************************************/
void test(int *v, int size) {
  int i;
  int error;

  error = 0;
  for (i = 0; i < size - 1; i++)
    if (v[i] > v[i + 1]) {
      error = 1;
      break;
    }

  if (error) 
    printf("ERROR: Not sorted. Elements %d and %d. (%d, %d)\n", i, i+1, v[i], v[i+1]); 
  else
    printf("Array sorted. first: %d last: %d\n", v[0], v[size-1]);
}
/*****************************/
/* Quicksortcclasico (Wirth) */
/*****************************/
void qsSeq(int *v, int first, int last) {
  int i, j, pivot, temp;
  double aux;

  i = first;
  j = last;
  aux = 1.0 * (double)v[first] + (double)v[last] + (double)v[(first + last) / 2];
  pivot = (int)(aux / 3.0);
  do {
    while (v[i] < pivot)
      i++;
    while (pivot < v[j])
      j--;
    if (i <= j) {
      temp = v[i];    /* intercambiar v[i] y v[j] */
      v[i] = v[j];
      v[j] = temp;
      i++;
      j--;
     }
   } while (i <= j);
   if (first < j)
     qsSeq(v, first, j);
   if (i < last)
     qsSeq(v, i, last);
}
